//
//  ArrayUtil.m
//  AlgorithmDemo
//
//  Created by zxs on 2020/8/21.
//  Copyright © 2020 zxs. All rights reserved.
//

#import "ArrayUtil.h"

@implementation ArrayUtil

#pragma mark - 数组归并
// 合并数组；其中a，b都是从小到大有序排列的数组
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
    int p = 0; // 遍历数组a的指针
    int q = 0; // 遍历数组b的指针
    int i = 0; // 记录当前存储位置
    
    // 任一数组没有到达边界则进行遍历
    while (p < aLen && q < bLen) {
        // 如果a数组对应位置的值小于b数组对应位置的值
        if (a[p] <= b[q]) {
            // 存储a数组的值
            result[i] = a[p];
            // 移动a数组的遍历指针
            p++;
        } else {
            // 存储b数组的值
            result[i] = b[q];
            // 移动b数组的遍历指针
            q++;
        }
        // 指向合并结果的下一个存储位置
        i++;
    }
    
    // 如果a数组有剩余
    while (p < aLen) {
        // 将a数组剩余部分拼接到合并结果的后面
        result[i] = a[p++];
        i++;
    }
    
    // 如果b数组有剩余
    while (q < bLen) {
        // 将b数组剩余部分拼接到合并结果的后面
        result[i] = b[q++];
        i++;
    }
}

#pragma mark - 快速排序

// 快速排序
void quickSort(int array[], int low, int high) {
    // 递归调用
    // 退出条件：low == high，意味着所有元素都排好了
    if (low < high) {
        // 调用1次划分，就排好了1个元素。返回基准数所在的下标，用来划分左右子数组
        int baseIndex = patition(array, low, high);
        // 分而治之，左边
        quickSort(array, low, baseIndex - 1);
        // 分而治之，右边
        quickSort(array, baseIndex + 1, high);
    }
}

// 一次数据划分：以第1个元素为基准，大的放右边，小的放左边，返回分界点的位置；
int patition (int array[], int low, int high) {
    // 以第1个元素作为基准
    int base = array[low];
    
    // 这里的low、high是形参，数值改变不影响实参本身
    while (low < high) {
        // 大于基准的数放右边
        while ((low < high) && base <= array[high]) {
            high--;
        }
        swap(array, low, high);
        
        // 小于基准的数放左边
        while ((low < high) && base >= array[low]) {
            low++;
        }
        swap(array, low, high);
    }
    
    // 返回数据划分之后，基准数所在的下标。时low == high
    return low;
}

// 交换数组不同下标对应的两个值
void swap(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

@end
